package org.example.sortdemo;

import java.util.Arrays;
import java.util.Random;

/**
 * @author: knowno
 * @create: 2025-09-10 14:18
 * @Version 1.0
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[10];
        Random random = new Random();
        //随机值初始化数组
        for (int i = 0; i < arr.length ; i++) {
            arr[i] = random.nextInt(100);
        }

        System.out.println("原始数组元素"+Arrays.toString(arr));
        //调用排序函数
        quickSorting(arr, 0, arr.length - 1);

        System.out.println("排序后的元素:"+Arrays.toString(arr));
    }


    /**
     * 快速排序
     */
    public  static  void quickSorting(int[] arr,int low,int high){
        //结束条件
        if (low>=high){
            return;
        }
        //设置基准位置,从最左侧开始
        int pivot = arr[low];
        System.out.println("基准位置:"+pivot);
        //设置左右指针 ,left从左向右移动,right从右向左侧移动
        int left = low;
        int right = high;

        //循环来处理指针的移动
        while (left < right){
            //从右侧开始找,找到比基准位置小的数
            while (arr[right]>=pivot && left<right){
                //右侧向左侧移动
                right--;
            }
            //从左侧开始找,找到比基准位置大的数
            while (arr[left]<=pivot && left<right){
                left++;
            }
            if (left < right) {
                //交换左右指针指向的元素
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //相遇的时候,当前的值和基准位置交换
        arr[low] = arr[left];
        arr[left] = pivot;

        if (low < left) {
            //递归处理基准位置左侧的元素
            quickSorting(arr, low, left - 1);
        }
        if (right < high) {
            //递归处理基准位置右侧的元素
            quickSorting(arr, right + 1, high);
        }

    }
}
